home *** CD-ROM | disk | FTP | other *** search
/ The 640 MEG Shareware Studio 2 / The 640 Meg Shareware Studio CD-ROM Volume II (Data Express)(1993).ISO / clang / jcool01.zip / BINARY_T.H < prev    next >
C/C++ Source or Header  |  1992-08-20  |  9KB  |  201 lines
  1. //
  2. // Copyright (C) 1991 Texas Instruments Incorporated.
  3. //
  4. // Permission is granted to any individual or institution to use, copy, modify,
  5. // and distribute this software, provided that this complete copyright and
  6. // permission notice is maintained, intact, in all copies and supporting
  7. // documentation.
  8. //
  9. // Texas Instruments Incorporated provides this software "as is" without
  10. // express or implied warranty.
  11. //
  12. // Created: MBN 06/28/89 -- Initial design and implementation
  13. // Updated: MBN 09/15/89 -- Added conditional exception handling
  14. // Updated: DKM 11/05/89 -- Replaced cache traversal with stack traversal
  15. //                          Also added support for AVL balancing
  16. // Updated: LGO 12/04/89 -- operator<< not inline
  17. // Updated: MBN 12/21/89 -- Added optional argument to set_compare method
  18. // Updated: MBN 02/20/90 -- Cut operators <, >, <=, >=; fixed operators ==, !=
  19. // Updated: MJF 06/30/90 -- Added base class name to constructor initializer
  20. // Updated: VDN 02/21/92 -- New lite version
  21. // Updated: JAM 08/19/92 -- modernized template syntax, remove macro hacks
  22. //
  23. // The Binary_Tree<Type> class is publicly derived  from the  Base_Binary_Tree class
  24. // and  implements simple, dynamic, sorted sequences.   Users requiring  a data
  25. // structure for  unsorted  sequences whose structure  and organization is more
  26. // under the control  of the programmer  are refered  to the N_Tree class.  The
  27. // Binary_Tree<Type>  class  is  a   friend   of the  Binary Node  class,  also
  28. // parameterized over the  same Type.  There is no  attempt made  to balance or
  29. // prune the tree.  Nodes  are added to  a particular sub-tree at the direction
  30. // of  the colating function.  As a  result, a tree parameterized  for integers
  31. // and that  uses the default integer  comparison operators whose  elements are
  32. // added in increasing order would result  in a lopsided  tree.  Likewise after
  33. // many items have been added and removed.
  34. //
  35. // The Binary_Tree<Type> class supports  the concept of  a current position  as
  36. // the tree is  traversed via  next, prev,  and find.   method that changes the
  37. // tree structure invalidates the current position state
  38. //
  39. // The  Binary_Tree<Type>  class supports   the concept of  a current position.
  40. // Once  the  current position is  initialized, the first  call  to advance the
  41. // current position causes an internal dynamic cache of pointers to nodes to be
  42. // created.  This cache is created by  an inorder traversal  of the tree. Other
  43. // current  position  advance and  decrement methods then  act  based  upon the
  44. // information in  the  cache.  Any  method  that changes  the  tree  structure
  45. // invalidates the cache.
  46. //
  47. // There are two  public constructors. The first takes  no arguments and simply
  48. // allocates initial storage for a  Binary_Tree<Type> object.  The second takes
  49. // a reference to an existing Binary_Tree<Type> object  and duplicates its size
  50. // and contents.  The Binary_Tree<Type> class has four private data slots.  The
  51. // first contains a pointer to the root of  the  tree, the second maintains the
  52. // current  position, the   third   contains a  pointer  to a  dynamic cache of
  53. // pointers to nodes used  by  the current  position  methods, and  the  fourth
  54. // contains a pointer  to the default  node comparison function.   In addition,
  55. // there are two private  methods.  The  first  is used  to create the cache of
  56. // pointers to nodes upon the first dispatch  to  advance the current position,
  57. // and the second is  the default  node  comparison function to  be used if the
  58. // user does not chose to provide one.
  59. //
  60. // Methods are available to put, remove, and find a node in a tree.  The reset,
  61. // next, prev, value,  remove, and find  methods provide a mechanism to iterate
  62. // through the nodes of  a tree based  upon the current position.  In addition,
  63. // all nodes can  be  removed from the  tree with  the clear method.  A balance
  64. // method is provided to allow  the user to shake the  tree at some appropriate
  65. // time in  order  to balance  the  left and  right  sub-trees.  This  might be
  66. // particularly useful in the case of static binary  trees, where the structure
  67. // becomes fixed and the impetus for fast, efficient searches is high. Finally,
  68. // the  equality, inequality,  less   than,  and greater  than    operators are
  69. // overloaded to provide node comparison functionality.
  70. //
  71.  
  72. #ifndef BINARY_TREEH                // If no definition for class
  73. #define BINARY_TREEH
  74.  
  75. #ifndef BASE_BINARY_TREEH            // If no definition for class
  76. #include <cool/Base_Binary_Tree.h>        // Include definition file
  77. #endif
  78.  
  79. #ifndef BINARY_NODEH                // If no definition for class
  80. #include <cool/Binary_Node.h>            // include definition file
  81. #endif
  82.  
  83. template <class Type>
  84. class CoolBinary_Tree : public CoolBase_Binary_Tree {
  85. public:
  86.   typedef int (*Compare)(const Type&, const Type&);
  87.  
  88.   CoolBinary_Tree();                // Simple constructor
  89.   CoolBinary_Tree(const CoolBinary_Tree<Type>&);    // Copy constructor
  90.   ~CoolBinary_Tree();                // Destructor 
  91.  
  92.   Boolean find (const Type&);            // Find value in tree
  93.  
  94.   Type& value ();                // Return value at current pos
  95.   inline CoolBinary_Node<Type>* get_root () const; // Return root node
  96.   inline CoolBinary_Node<Type>* node ();       // Return current node
  97.   inline Boolean remove ();            // Remove node at current pos
  98.   inline Boolean put (const Type&);        // Add value to tree 
  99.   inline Boolean remove (const Type&);        // Remove value from tree
  100.   CoolBinary_Tree<Type>& operator= (CoolBinary_Tree<Type>&); // Assignment operator
  101.   void balance ();                // Balance the tree
  102.  
  103.   void set_compare (Compare = NULL); // Set compare function
  104.   Boolean operator== (CoolBinary_Tree<Type>&);        // Overload equality
  105.   inline Boolean operator!= (CoolBinary_Tree<Type>&);    // Overload not equal
  106.  
  107.   friend ostream& operator<< (ostream&, const CoolBinary_Tree<Type>&);
  108.   /*inline##*/ friend ostream& operator<< (ostream&, const CoolBinary_Tree<Type>*);
  109.  
  110. protected:
  111.   Boolean put_internal    (const Type&, Boolean avl=NULL);// adds a node
  112.   Boolean remove_internal (const Type&, Boolean avl=NULL);// removes a node
  113.   inline CoolBinary_Node<Type>* copy_nodes(const CoolBinary_Node<Type>*) const; // Copy subnodes
  114.  
  115. private:
  116.   Compare compare;            // Compare function
  117.   CoolBinary_Node<Type>* baltree (long);    // Build balanced subtree
  118.   friend void print_tree (const CoolBinary_Node<Type>*, ostream&);
  119.   friend int default_node_compare (const Type&, const Type&);
  120. };
  121.  
  122.  
  123. // get_root -- return node that roots this tree
  124. // Input:      None
  125. // Output:     Pointer to CoolBinary_Node of type Type.
  126.  
  127. template <class Type>
  128. inline CoolBinary_Node<Type>* CoolBinary_Tree<Type>::get_root () const {
  129.   return (CoolBinary_Node<Type>*)CoolBase_Binary_Tree::get_root ();
  130. }
  131.  
  132. // node -- return node pointed to by the current position
  133. // Input:      None
  134. // Output:     Pointer to CoolBinary_Node of type Type.
  135.  
  136. template <class Type>
  137. inline CoolBinary_Node<Type>* CoolBinary_Tree<Type>::node () {
  138.   return (CoolBinary_Node<Type>*)CoolBase_Binary_Tree::node ();
  139. }
  140.  
  141. // put -- Add a value to the sorted binary tree if it is not already there
  142. // Input: Reference to value to add to tree
  143. // Output: TRUE if item added, FALSE otherwise
  144.  
  145. template <class Type>
  146. inline Boolean CoolBinary_Tree<Type>::put (const Type& value) {
  147.   return this->put_internal (value);
  148. }
  149.  
  150.  
  151. // remove -- Remove a value from the sorted binary tree. Deletion of a node
  152. //           that has both left and right subtrees is done by descending down 
  153. //           the rightmost branch of the left subtree of the element to be
  154. //           deleted until a leaf is encountered, at which point the change is
  155. //           propagated back.
  156. // Input:    Reference to value to remove
  157. // Output:   TRUE if item removed, FALSE otherwise
  158.  
  159. // For a Binary Tree, call remove_internal without the avl flag
  160. template <class Type>
  161. inline Boolean CoolBinary_Tree<Type>::remove (const Type& value) {
  162.   return this->remove_internal(value);
  163. }
  164.  
  165.  
  166. // remove -- Remove node at current position in the tree
  167. // Input:    None
  168. // Output:   Value of node removed from tree
  169.  
  170. template <class Type>
  171. inline Boolean CoolBinary_Tree<Type>::remove () {
  172.   return this->remove_internal (this->value());
  173. }
  174.  
  175.  
  176.  
  177. // operator<< -- Output a binary tree by printing it sideways where the root is
  178. //               printed at the left margin. To obtain the normal orientation,
  179. //               rotate the output 90 degrees clockwise
  180. // Input:        Reference to output stream, reference to CoolBinary_Tree<Type>
  181. // Output:       Reference to output stream
  182.  
  183. template <class Type>
  184. inline ostream& operator<< (ostream& os, const CoolBinary_Tree<Type>* b) {
  185.   return os << *b;
  186. }
  187.  
  188.  
  189. // operator!= -- Compare binary trees for different values and/or structure
  190. // Input:        constant reference to another binary tree
  191. // Output:       TRUE/FALSE
  192.  
  193. template <class Type>
  194. inline Boolean CoolBinary_Tree<Type>::operator!=(CoolBinary_Tree<Type>& t) {
  195.   return (! (*this == t));
  196. }
  197.  
  198. #endif                        // End BINARY_TREEH #if
  199.  
  200.  
  201.